/*      > C.Map - Map data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "map.h"

#ifdef test
#include <stdio.h>
#endif

/* Return values from functions */

#define OK      1
#define ERR     0

/* Utility function - find a binding in a map */

static link find (const map m, const void *domain, int *bucket, link *prev)
{
        link this;
        link p;
        int i;

        p = NULL;
        i = (m->hash)(domain) % m->buckets;

        if ( bucket != NULL )
                *bucket = i;

        this = m->bucket[i];

        while ( this != NULL )
        {
                if ( memcmp(domain,this->data,m->domain_size) == 0 )
                {
                        if ( prev != NULL )
                                *prev = p;

                        return this;
                }
                else
                {
                        p = this;
                        this = this->next;
                }
        }

        if ( prev != NULL )
                *prev = p;

        return NULL;
}

/* General component routines */

map map_new (int domain_len, int range_len, int buckets, int (*hash)(const void *))
{
        register map m;
        int i;

        m = malloc(sizeof(struct map));

        if ( m == NULL )
                return NULL;

        m->bucket = malloc(buckets * ( sizeof(struct link) - 1 ));
        if ( m->bucket == NULL )
        {
                free(m);
                return NULL;
        }

        for ( i = 0; i < buckets; ++i )
                m->bucket[i] = NULL;

        m->hash = hash;
        m->buckets = buckets;
        m->domain_size = domain_len;
        m->range_size = range_len;

        return m;
}

void map_free (map m)
{
        map_clear(m);
        free(m->bucket);
        free(m);
}

void map_clear (map m)
{
        int i;
        link this_entry;
        link next_entry;

        for ( i = 0; i < m->buckets; ++i )
        {
                this_entry = m->bucket[i];

                while ( this_entry != NULL )
                {
                        next_entry = this_entry->next;
                        free(this_entry);
                        this_entry = next_entry;
                }

                m->bucket[i] = NULL;
        }
}

int map_copy (map m1, const map m2)
{
        link from, to;
        link new;
        int size;
        int i;

        if ( m1->domain_size != m2->domain_size )
                return ERR;

        if ( m1->range_size != m2->range_size )
                return ERR;

        if ( m1->buckets != m2->buckets )
                return ERR;

        if ( m1->hash != m2->hash )
                return ERR;

        map_clear(m1);

        size = m2->domain_size + m2->range_size;

        for ( i = 0; i < m2->buckets; ++i )
        {
                from = m2->bucket[i];

                if ( from == NULL )
                        m1->bucket[i] = NULL;
                else
                {
                        new = malloc(sizeof(struct link) - 1 + size);

                        if ( new == NULL )
                        {
                                map_clear(m1);
                                return ERR;
                        }

                        memcpy(new->data,from->data,size);
                        new->next = NULL;
                        m1->bucket[i] = new;

                        to = new;
                        from = from->next;

                        while ( from != NULL )
                        {
                                new = malloc(sizeof(struct link) - 1 + size);

                                if ( new == NULL )
                                {
                                        map_clear(m1);
                                        return ERR;
                                }

                                memcpy(new->data,from->data,size);
                                new->next = NULL;

                                to->next = new;

                                to = to->next;
                                from = from->next;
                        }
                }
        }

        return OK;
}

int map_equal (const map m1, const map m2)
{
        link p1;
        link p2;
        void *v1;
        void *v2;
        int count1;
        int count2;
        int i;
        int d_size;
        int r_size;

        if ( m1->domain_size != m2->domain_size )
                return 0;

        if ( m1->range_size != m2->range_size )
                return 0;

        if ( m1->buckets != m2->buckets )
                return 0;

        if ( m1->hash != m2->hash )
                return 0;

        d_size = m1->domain_size;
        r_size = m1->range_size;

        for ( i = 0; i < m1->buckets; ++i )
        {

                if ( m1->bucket[i] == NULL && m2->bucket[i] != NULL )
                        return 0;

                if ( m2->bucket[i] == NULL && m1->bucket[i] != NULL )
                        return 0;

                p1 = m1->bucket[i];
                count1 = 0;

                while ( p1 != NULL )
                {
                        v1 = &p1->data[0];

                        for ( p2 = m2->bucket[i]; p2 != NULL; p2 = p2->next )
                        {
                                v2 = &p2->data[0];
                                if ( memcmp(v1,v2,d_size) == 0 )
                                        break;
                        }

                        if ( p2 == NULL )
                                return 0;

                        v1 = &p1->data[d_size];
                        v2 = &p2->data[d_size];
                        if ( memcmp(v1,v2,r_size) != 0 )
                                return 0;

                        ++count1;

                        p1 = p1->next;
                }

                count2 = 0;

                for ( p2 = m2->bucket[i]; p2 != NULL; p2 = p2->next )
                        ++count2;

                if ( count1 != count2 )
                        return 0;
        }

        return 1;
}

int map_empty (const map m)
{
        int i;

        for ( i = 0; i < m->buckets; ++i )
                if ( m->bucket[i] != NULL )
                        return 0;

        return 1;
}

int map_size (const map m)
{
        link p;
        int i;
        int count = 0;

        for ( i = 0; i < m->buckets; ++i )
        {
                for ( p = m->bucket[i]; p != NULL; p = p->next )
                        ++count;
        }

        return count;
}

int map_iterate (const map m, int (*process)(void *, void *))
{
        link p;
        int i;
        int ret;
        void *domain;
        void *range;

        for ( i = 0; i < m->buckets; ++i )
        {
                for ( p = m->bucket[i]; p != NULL; p = p->next )
                {
                        domain = &p->data[0];
                        range = &p->data[m->domain_size];

                        ret = process(domain,range);

                        /* Non-zero => stop processing here */
                        /* Negative => Abnormal (error) termination */

                        if ( ret != 0 )
                                return ( ret >= 0 );
                }
        }

        return OK;
}

/* Map-specific routines */

int map_bind (map m, const void *domain_val, const void *range_val)
{
        link this;
        link new;
        int i;

        this = find(m,domain_val,&i,NULL);

        if ( this != NULL )
                return ERR;

        new = malloc(sizeof(struct link) - 1 + m->domain_size + m->range_size);

        if ( new == NULL )
                return ERR;

        memcpy(&new->data[0],domain_val,m->domain_size);
        memcpy(&new->data[m->domain_size],range_val,m->range_size);
        new->next = m->bucket[i];

        m->bucket[i] = new;

        return OK;
}

int map_unbind (map m, const void *domain_val)
{
        link this;
        link prev;
        int i;

        this = find(m,domain_val,&i,&prev);

        if ( this == NULL )
                return ERR;

        if ( prev == NULL )
                m->bucket[i] = this->next;
        else
                prev->next = this->next;

        free(this);

        return OK;
}

void *map_value (const map m, const void *domain_val)
{
        link this;

        this = find(m,domain_val,NULL,NULL);

        if ( this == NULL )
                return NULL;
        else
                return &this->data[m->domain_size];
}

int map_bound (const map m, const void *domain_val)
{
        return ( find(m,domain_val,NULL,NULL) != NULL );
}

/*---------------------------------------------------------------------------*/

#ifdef test
int print (void *domain, void *range)
{
        printf("   %d->%d\n",*(int *)domain,*(int *)range);
        return STATUS_CONTINUE;
}

void map_dump (map m)
{
        printf("map:\n");
        map_iterate(m,print);
}
#endif

/*---------------------------------------------------------------------------*/

#ifdef test

#define BUFLEN 255

int hash (const void *n)
{
        return *(int *)n;
}

int main (void)
{
        char buf[BUFLEN];
        int i, j, from, to;
        map m[10];

        for ( i = 0; i < 10; ++i )
                m[i] = map_new(sizeof(int),sizeof(int),10,hash);

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                if ( buf[0] == '\n' || buf[0] == '\0' )
                        continue;
                else if ( sscanf(buf,"clear %1d",&i) == 1 )
                        map_clear(m[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        map_copy(m[i],m[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(map_equal(m[i],m[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(map_empty(m[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",map_size(m[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        map_dump(m[i]);
                else if ( sscanf(buf,"bind %1d %d %d",&i,&from,&to) == 3 )
                {
                        if ( !map_bind(m[i],&from,&to) )
                                printf("Already bound\n");
                }
                else if ( sscanf(buf,"unbind %1d %d",&i,&from) == 2 )
                {
                        if ( !map_unbind(m[i],&from) )
                                printf("Not bound\n");
                }
                else if ( sscanf(buf,"value %1d %d",&i,&from) == 2 )
                {
                        int *p = map_value(m[i],&from);
                        if ( p == NULL )
                                printf("Unbound\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( sscanf(buf,"bound %1d %d",&i,&from) == 2 )
                        printf("%s\n",(map_bound(m[i],&from) ? "yes" : "no"));
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        printf("Deleting m[0-9]\n");
        for ( i = 0; i < 10; ++i )
                map_free(m[i]);

        return 0;
}

#endif
